public class Solution1774 {

    int ans=Integer.MAX_VALUE;

    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
        for (int i=0;i<baseCosts.length;i++){
            dfs(baseCosts,toppingCosts,target,0,baseCosts[i]);
        }
        return ans;
    }

    private void dfs(int[] baseCosts, int[] toppingCosts, int target, int k, int now) {
        if (k==toppingCosts.length){
            ans=compare(now,ans,target);
            return;
        }
        dfs(baseCosts,toppingCosts,target,k+1,now);
        dfs(baseCosts,toppingCosts,target,k+1,now+toppingCosts[k]);
        dfs(baseCosts,toppingCosts,target,k+1,now+toppingCosts[k]*2);
    }

    private int compare(int a, int ans, int target) {
        if (Math.abs(a-target)<Math.abs(ans-target)){
            return a;
        }else if (Math.abs(a-target)==Math.abs(ans-target)){
            return Math.min(a,ans);
        }else {
            return ans;
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution1774().closestCost(new int[]{1,7},new int[]{3,4},10));
    }
}
